/** 基于邻接矩阵实现的无向图 */
class GraphAdjMatrix {
  vertices: number[]; // 顶点集合
  adjMat: number[][]; // 邻接矩阵

  constructor(vertices: number[], edges: number[][]) {
    this.vertices = [];
    this.adjMat = [];
    // 添加顶点
    vertices.forEach(v => this.addVertex(v));
    // 添加边
    // 注意：edges 元素代表顶点索引，即对应 vertices 元素索引
    edges.forEach(([v, w]) => {
      this.addEdge(v, w);
    });
  }
  /** 获取顶点数量 */
  getSize(): number {
    return this.vertices.length;
  }
  /** 添加顶点 */
  addVertex(val: number): void {
    const size = this.getSize();
    // 向顶点列表中添加新顶点的值
    this.vertices.push(val);
    // 在邻接矩阵中添加一行
    const row = new Array(size).fill(0);
    this.adjMat.push(row);
    // 在邻接矩阵中添加一列
    this.adjMat.forEach(row => {
      row.push(0);
    });
  }
  /** 删除顶点 */
  removeVertex(index: number): void {
    if (index >= this.getSize()) return;
    // 在顶点列表中移除索引为 index 的顶点
    this.vertices.splice(index, 1);
    // 在邻接矩阵中移除索引为 index 的行
    this.adjMat.splice(index, 1);
    // 在邻接矩阵中移除索引为 index 的列
    this.adjMat.forEach(row => {
      row.splice(index, 1);
    });
  }
  /** 添加边 */
  addEdge(v: number, w: number): void {
    // 索引越界与相等处理，即顶点不存在或为自身
    if (v < 0 || v >= this.getSize() || w < 0 || w >= this.getSize() || v === w) {
      return;
    }
    // 在无向图中，邻接矩阵沿主对角线对称，即满足 (v, w) === (w, v)
    this.adjMat[v][w] = 1;
    this.adjMat[w][v] = 1;
  }
  /** 删除边 */
  removeEdge(v: number, w: number): void {
    // 索引越界与相等处理，即顶点不存在或为自身
    if (v < 0 || v >= this.getSize() || w < 0 || w >= this.getSize() || v === w) {
      return;

    }
    // 在无向图中，邻接矩阵沿主对角线对称，即满足 (v, w) === (w, v)
    this.adjMat[v][w] = 0;
    this.adjMat[w][v] = 0;
  }

}

// 示例
const vertices = [1, 3, 2, 5, 4];
const edges = [
  [0, 1],
  [0, 3],
  [1, 2],
  [2, 3],
  [2, 4],
  [3, 4],
  [4, 5]
]
const graph = new GraphAdjMatrix(vertices, edges);
graph.adjMat.forEach(row => console.log(row));

/** 基于邻接表实现的无向图 */
class GraphAdjList {
  adjList: Map<number, number[]>; // 邻接表

  constructor(edges: number[][]) {
    this.adjList = new Map();
    // 添加边
    // 注意：edges 元素代表顶点索引，即对应 vertices 元素索引
    edges.forEach(([v, w]) => {
      this.addVertex(v);
      this.addEdge(v, w);
    });
  }
  /** 获取顶点数量 */
  getSize(): number {
    return this.adjList.size;
  }
  /** 添加顶点 */
  addVertex(v: number): void {
    if (!this.adjList.has(v)) {
      this.adjList.set(v, []);
    }
  }
  /** 删除顶点 */
  removeVertex(v: number): void {
    if (!this.adjList.has(v)) {
      return;
    }
    // 在邻接表中删除索引为 v 的顶点
    this.adjList.delete(v);
    // 遍历其他顶点的邻接表，删除所有包含 v 的边
    this.adjList.forEach(adj => {
      const index = adj.indexOf(v);
      if (index !== -1) {
        adj.splice(index, 1);
      }
    })
  }
  /** 添加边 */
  addEdge(v: number, w: number): void {
    // 顶点不存在则跳过
    if (!this.adjList.has(v) || !this.adjList.has(w)) {
      return;
    }
    // 保证 v 的邻接表不包含 w
    if (!this.adjList.get(v)!.includes(w)) {
      this.adjList.get(v)!.push(w);
    }
    // 保证 w 的邻接表不包含 v
    if (!this.adjList.get(w)!.includes(v)) {
      this.adjList.get(w)!.push(v);
    }
  }
}